package com.mdnote.practice.plus_search.prune;

import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/26
 * @description N皇后问题
 */
public class LeetCode51 {


    public static void main(String[] args) {
        LeetCode51 leetCode51 = new LeetCode51();
        List<List<String>> resList = leetCode51.solveNQueens(4);
        for (List<String> strings : resList) {
            System.out.println(strings);
        }
    }
    public List<List<String>> solveNQueens(int n) {
        if (n < 1) {
            return new ArrayList<>();
        }
        // 主要考察剪纸
        // 创建三个哈希表
        Set<Integer> shu = new HashSet<>();
        Set<Integer> pie = new HashSet<>();
        Set<Integer> na = new HashSet<>();

        // 结果集
        List<List<String>> resList = new ArrayList<>();
        _solveNQueen(0, n, "", shu, pie, na, resList);
        return resList;
    }

    private void _solveNQueen(int row, int max_level, String res, Set<Integer> shu, Set<Integer> pie, Set<Integer> na, List<List<String>> resList) {
        // Terminator
        if (row == max_level) {
            resList.add(toBoard(res));
            return;
        }
        // Process

        for (int col = 0; col < max_level; col++) {
            if (!shu.contains(col) && !pie.contains(row + col) && !na.contains(row - col)) {
                shu.add(col);
                pie.add(row + col);
                na.add(row - col);
                // Drill down
                _solveNQueen(row + 1, max_level, res + col, shu, pie, na, resList);
                // Restore current logic
                shu.remove(col);
                pie.remove(row + col);
                na.remove(row - col);

            }
        }
    }

    private List<String> toBoard(String res) {
        List<String> resList = new ArrayList<>();
        for (int i = 0; i < res.length(); i++) {
            char[] chars = new char[res.length()];
            Arrays.fill(chars, '.');
            chars[res.charAt(i) - 48]  = 'Q';
            resList.add(new String(chars));
        }
        return resList;
    }
}
